The present invention relates to computer imaging and more particularly to method and apparatus for converting functional animations into a form that can be efficiently updated at a rate required for visual presentation on a video display.
Computer generated animations have wide applications and have improved as hardware has improved. As the personal computer industry has evolved into a multi-billion dollar economy, high quality graphics rendering systems have become less expensive. Graphics systems once costing many hundreds of thousands of dollars are now available at a fraction of that cost.
A standard means of displaying images on a viewing screen is to first format the image into a bitmapped image and transfer the bitmapped image to a region of video memory. As the computer is composing a next subsequent bitmapped image video hardware accesses the first region of video memory that was previously formatted and causes video signals to be generated and coupled to a viewing monitor. Once the next subsequent region of memory has been formatted, the video hardware switches to the memory region containing that bitmapped image to generate appropriate video driver signals. This back and forth switching occurs at video refresh rates of display rates of at least 60 frames per second.
Lower level presentation libraries for sprite-based display and sound presentation are designed not for convenience of a program""s author or readers, but rather for efficient execution on anticipated video and/or audio hardware. These presentation libraries impose rigid structure, in order to allow acceleration by hardware and low level software. Programs written directly on top of these libraries must adapt to relatively inflexible representations and tend to be relatively non-modular. Writing software that directly interfaces the presentation libraries is not an easy task and to successfully program for these libraries one must adher to the hardware protocols rather closely. The rigorous adherence to video presentation standards can make the process of producing an effective animation more difficult. There are existing programming languages that are well suited to accomplishing animation in a more intuitive way. A functional approach to animation offers considerable flexibility and modularity and is described, for example, in Arya, Kavi, xe2x80x9cA Functional Animation Starter-Kit,xe2x80x9d Journal of Functional Programming, Vol. 4, No. 1, pp. 1-18 (January 1994), and in Elliott, Conal, and P. Hudak, xe2x80x9cFunctional Reactive Animation,xe2x80x9d Proceedings of the 1997 ACM SIGPLAN International Conference on Functional Programming, Amsterdam, The Netherlands, pp. 263-273 (Jun. 9-11, 1997), which is herein incorporated by reference. Functional animation encourages a highly modular programming style by supplying a set of arbitrarily composable functions for building up animations.
These functional programming languages treat animations as values or elements of a data type consisting of a set of constants and combining operators. The use of an animation data type allows great flexibility in composing these basic building blocks into either directly useful or attractive animations, or new building blocks, parameterized as desired. Moreover, animation is a polymorphic notion since the functions implementing the animation can be applied to different types. Animation can be applied to 2D images, 3D geometry, and constituent types like colors, points, vectors, numbers, booleans, etc. Consequently, there is not just one type, but a collection of types and type constructors. Such a system of data types imposes just enough discipline to rule out nonsensical compositions (such as rotating by the angle xe2x80x9cpurplexe2x80x9d), without inhibiting the author""s creativity. In this way, the data types are designed to serve the need of the author (and readers) of an animation.
A computer animation system constructed in accordance with the invention animates a computer presentation that includes both images and sound. A component referred to as a normalizer interprets an animation to produce a data structure of image and sound objects. At video and audio refresh rates this data structure is in turn interpreted by a rendering software component referred to herein as a sprite engine.
The exemplary embodiment of the invention renders the animation by first describing or defining the computer animation in a high level functional programming language program. At presentation update intervals the contents of a presentation data structure are updated based on the time varying computer presentation. At presentation refresh intervals more frequent than the update intervals, a computer presentation data set is composed that approximates a change of the computer presentation between the update intervals. At a sensory presentation rate greater than a rate at which the presentation data structure is updated, the computer presentation data is sent to rendering hardware to perform the computer animation.
Computer animation typically involves a visual images that are periodically updated. The presentation data structure for this type animation includes a sequence of images that are displayed on a viewing monitor. In a bitmapped imaging process, the visual image description is data that is stored in a region of the computer memory. The frequency of the presentation refresh rate is high enough to smoothly update such video images.
The computer animation may also include an audible rendering. For an audible animation the frequency and volume of the output signal is updated rather than updating a part of memory.
In accordance with an exemplary embodiment of the invention, the presentation data structure is a sprite tree. The sprite tree is made up of a series of nodes with sprites at the leaves and behavior modifications at interior nodes of the sprite tree. The sprite interpreter or sprite engine animates the sprites that make up the sprite tree by performing a xe2x80x98paintxe2x80x99 function for each sprite leaf in the tree. In the instance of a sound sprite the xe2x80x98paintxe2x80x99 method provides an audible output from an audible hardware interface.
Use of a sprite tree datastructure facilitates the updating of the animation. Updating of the sprite tree data structure may only require an updating of a portion of the sprite tree affected by a user controlled input. This requires a replacement of an internal node of the sprite tree and all sprites descending from this so-called mutable node but does not require a complete re-construction of the sprite tree.
A normalizer component updates sprite positions much less frequently than needed to achieve video refresh rates. Between successive updates of the sprite tree the sprite tree engine renders the sprites at positions intermediate the end points determined by the normalizer component. The positions of these intermediate positions are determining by linearly interpolating between the two end points.
In one embodiment of the present invention, the computer animation is represented in a high level programming language such as Haskell (note, other functional animation programming languages could also be used) which allows the animation to be more easily programmed. This high level animation representation is converted by the normalizer component into a presentation data structure based on the time varying computer presentation defined in the Haskell program. The normalizer component defines a series of different methods that convert legal constructs from the Haskell representation to the presentation data structure by determining which of said different methods matches the Haskell animation representation. The sprite tree engine composes a bit mapped image from the data in the presentation data structure at refresh intervals and transmits the computer presentation data to rendering hardware to perform the computer animation. The preferred normalizer component recursively calls the methods until the method includes an instruction to add a sprite (image or sound) to a list of sprite trees.
A preferred computer for practicing the invention includes an operating system that can spawn multiple executing threads. In such an environment the step of updating the contents of the presentation data structure executes in a first thread and the step of accessing data stored in the data structure and composing computer presentation data executes in a second thread. The second thread executes in a higher priority thread.
These and other objects, advantages and features of the invention will become better understood from the disclosed exemplary embodiment of the present invention which is described in conjunction with the accompanying drawings.